package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * https://leetcode.com/problems/same-tree/
 *
 * @author tzp
 * @since 2020/9/14
 */
public class LC100 implements TreeProblem {
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        // p and q are both null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.right, q.right) &&
                isSameTree(p.left, q.left);
    }

    //写的什么几把玩意
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null) {
            return q == null;
        } else {
            if (q == null) {
                return false;
            }
        }
        Deque<TreeNode> deque1 = new ArrayDeque<>();
        deque1.add(p);
        Deque<TreeNode> deque2 = new ArrayDeque<>();
        deque2.add(q);
        while (deque1.size() != 0) {
            TreeNode n1 = deque1.pollFirst();
            TreeNode n2 = deque2.pollFirst();
            if (n2 == null || n1.val != n2.val) {
                return false;
            }
            if (n1.left != null) {
                if (n2.left == null) {
                    return false;
                } else {
                    deque1.addLast(n1.left);
                    deque2.addLast(n2.left);
                }
            } else {
                if (n2.left != null) {
                    return false;
                }
            }

            if (n1.right != null) {
                if (n2.right == null) {
                    return false;
                } else {
                    deque1.addLast(n1.right);
                    deque2.addLast(n2.right);
                }
            } else {
                if (n2.right != null) {
                    return false;
                }
            }
        }
        return deque2.size() == 0;
    }
}
